# 作者：石吴震
# 2025年01月08日10时07分34秒
# 474160957@qq.com


class Node():
    def __init__(self,val=-1,lchild=None,rchild=None):
        self.val = val
        self.lchild = lchild
        self.rchild = rchild

class Binary_tree():
    def __init__(self):
        self.root = None  # 根节点
        self.help_list = []  # 辅助列表

    def level_create_tree(self,node:Node):
        if self.root is None:  # 如果树为空，则添加根节点
            self.root = node
            self.help_list.append(node)
        else:
            self.help_list.append(node)
            if self.help_list[0].lchild is None:  # 如果左子树为空，则添加左子树
                self.help_list[0].lchild = node
            else:
                self.help_list[0].rchild = node      # 如果左子树不为空，则添加右子树
                self.help_list.pop(0)  # 弹出第一个元素，准备添加下一个元素,del self.help_list[0]也可以
    def pre_order(self,cur_node:Node):
        if cur_node:
            print(cur_node.val,end=' ')
            self.pre_order(cur_node.lchild)
            self.pre_order(cur_node.rchild)
    def in_order(self,cur_node:Node):
        if cur_node:
            self.in_order(cur_node.lchild)
            print(cur_node.val,end=' ')
            self.in_order(cur_node.rchild)
    def post_order(self,cur_node:Node):
        if cur_node:
            self.post_order(cur_node.lchild)
            self.post_order(cur_node.rchild)
            print(cur_node.val,end=' ')

    def level_order(self,cur_node:Node):
        help_list = []  # 创建辅助列表，这是局部变量，可以重名
        help_list.append(cur_node)  # 根节点入队
        while help_list:
            cur_node = help_list.pop(0)  # 队首出队
            print(cur_node.val,end=' ')
            if cur_node.lchild:  # 左子树入队
                help_list.append(cur_node.lchild)
            if cur_node.rchild:  # 右子树入队
                help_list.append(cur_node.rchild)

if __name__ == '__main__':
    tree = Binary_tree()  # 实例化树
    for i  in range(1,11):
        node = Node(i) #实例化节点

        tree.level_create_tree(node)   #创建树,把节点放树中

    tree.pre_order(tree.root)  # 先序遍历，即深度优先遍历
    print()
    tree.in_order(tree.root)  # 中序遍历
    print()
    tree.post_order(tree.root)  # 后序遍历
    print()
    tree.level_order(tree.root)  # 层序遍历
    print()



